package com.sicheng.蓝桥.练习题.基础图论.迷宫系列;

import java.util.ArrayDeque;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/17 14:48
 * https://mp.weixin.qq.com/s?__biz=Mzg4NDU4Njk2Nw==&mid=2247486257&idx=1&sn=e3ed0bd69b94599b139fd16f87d9a0ed&chksm=cfb4ab89f8c3229f0b1f81487b3af395db33c8562186442c4b4e18f50ad8f606771c0304cd35&mpshare=1&scene=23&srcid=0517XwTiX5ILIPg6ajxu8jBj&sharer_sharetime=1652770142735&sharer_shareid=59349a1aa1ad1301447caa8690fbe6fc#rd
 */
@SuppressWarnings("all")
public class 蚂蚁走迷宫 {


    /**
     * 输入数据：
     * 5 5
     * 0 0 -1 0 0
     * 0 0 0 0 -2
     * -1 0 -2 0 0
     * 0 0 0 -1 0
     * 0 -2 0 0 0
     * 1 1 4 3
     * <p>
     * 输出：
     * 已到目标点，最短距离为5
     */


    //实现步骤如下：
    //将起点加入队列。
    //从队首取出一个节点，通过该节点向4个方向扩展子节点，并依次加入队尾。
    //重复以上步骤，直至队空或已找到目标位置。
    public static void main(String[] args) {
        solve();
        printPath();

    }

    static ArrayDeque<int[]> path = new ArrayDeque<>();

    private static void printPath() {
        int i = X, j = Y;
        //存储具体的路径，如果只需要最短路径的大小,只需要用计数变量存储
        path.push(new int[]{i, j});
        while (!(i == x && j == y)) {
            int d = vis[i][j];
            if (d == 1) {
                path.push(new int[]{--i, j});
            } else if (d == 2) {
                path.push(new int[]{++i, j});
            } else if (d == 3) {
                path.push(new int[]{i, ++j});
            } else if (d == 4) {
                path.push(new int[]{i, --j});
            }
        }
        System.out.println(path.size() - 1);
    }

    private static int x;
    private static int y;
    private static int X;
    private static int Y;

    static int[][] vis;
    static int[][] g;
    static ArrayDeque<int[]> deque;

    private static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //存储迷宫
        g = new int[n][m];
        //上一个结点到(i,j) 的方向
        vis = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = scanner.nextInt();
            }
        }

        //起点坐标(x,y)
        x = scanner.nextInt();
        y = scanner.nextInt();
        //终点坐标(X,Y)
        X = scanner.nextInt();
        Y = scanner.nextInt();
        g[x][y] = -1;
        bfs(n, m);
    }

    private static void bfs(int n, int m) {
        deque = new ArrayDeque<>();
        deque.offer(new int[]{x, y});
        while (!deque.isEmpty()) {
            int[] last = deque.removeFirst();
            int i = last[0];
            int j = last[1];
            boolean ok = go(n, m, i, j);
            if (ok)
                return;
        }
    }

    // 走上下左右4个方向
    private static boolean go(int n, int m, int i, int j) {
        return doPass(n, m, i + 1, j, 1) ||
                doPass(n, m, i - 1, j, 2) ||
                doPass(n, m, i, j - 1, 3) ||
                doPass(n, m, i, j + 1, 4);
    }

    //经过终点返回true
    private static boolean doPass(int n, int m, int i, int j, int d) {
        if (i >= 0 && i < n && j >= 0 && j < m && isOk(i, j)) {
            g[i][j] = -1;
            vis[i][j] = d;
            deque.offer(new int[]{i, j});
        }
        return i == X && j == Y;
    }

    //能否走到(i,j)
    private static boolean isOk(int i, int j) {
        return g[i][j] == 0 && vis[i][j] == 0;
    }

}
